#define _CRT_SECURE_NO_WARNINGS 1
//向下调整函数 建立大堆
void AdjustDown(int* a, int n, int parent)
{
	int child = parent * 2 + 1; // 初始化child为parent的左孩子
	while (child < n) // 当child未越界时循环
	{
		if (child + 1 < n && a[child] < a[child + 1]) // 如果右孩子存在且左孩子大于右孩子
		{
			child++; // 将child指向右孩子
		}

		if (a[child] > a[parent]) // 如果孩子节点大于父节点，则违反了大堆的性质
		{
			Swap(&a[child], &a[parent]); // 交换孩子节点和父节点的值
			parent = child; // 更新parent为交换后的位置
			child = parent * 2 + 1; // 更新child为新的parent的左孩子
		}
		else
		{
			break; // 如果父节点已经不小于任何一个孩子节点，则调整完毕，退出循环
		}
	}
}
//堆排
void HeapSort(int* a, int n)
{
	for (int i = (n - 2) / 2; i >= 0; i--) // 从最后一个非叶子节点开始，直到根节点
	{
		AdjustDown(a, n, i); // 将每个非叶子节点调整为堆的形式
	}
	int end = n - 1;
	while (end > 0) // 当数组还有元素时
	{
		Swap(&a[0], &a[end]); // 将堆顶元素（当前最小值）与最后一个元素交换
		AdjustDown(a, end, 0); // 将剩余的元素重新调整为堆
		end--; // 减少堆的大小
	}
}